package leetcode.simple.q21;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 21. 合并两个有序链表
 */
public class Main {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 4};
        int[] nums2 = {1, 3, 4};

        //初始化链表
        ListNode listNode1 = createListNode(nums1);
        ListNode listNode2 = createListNode(nums2);

        //合并两个有序链表
        //ListNode listNode = mergeTwoLists(listNode1, listNode2);

        ListNode listNode = mergeTwoLists2(listNode1, listNode2);

        //输出结果
        System.out.println(listNode);

    }

    /**
     * 合并两个有序链表
     * @param l1 链表1
     * @param l2 链表2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        //做判空处理
        if (l1 == null && l2 == null){
            return null;
        }

        //将链表转化为数组
        int[] arr1 = listToArray(l1);
        int[] arr2 = listToArray(l2);

        //将2个数组合并
        //创建一个数组用来存放结果，长度为前面2个数组长度之和
        int[] arr = new int[arr1.length + arr2.length];
        //将第一个数组的元素转移到结果数组中
        for (int i = 0; i < arr1.length; i++) {
            arr[i] = arr1[i];
        }
        //将第二个数组的元素转移到结果数组中
        for (int i = arr1.length, j = 0; i < arr.length; i++, j++) {
            arr[i] = arr2[j];
        }

        //将结果数组排序
        Arrays.sort(arr);

        //将结果数组的内容存到链表中
        ListNode listNode = createListNode(arr);

        return listNode;
    }

    /**
     * 链表转数组
     * @param listNode
     * @return
     */
    public static int[] listToArray(ListNode listNode){
        //做判空处理
        if (listNode == null){
            return new int[0];
        }

        List<Integer> list = new ArrayList<>();
        ListNode pointer = listNode;

        //遍历链表
        while(true) {
            list.add(pointer.val);
            if (pointer.next != null){
                pointer = pointer.next;
            }else {
                break;
            }
        }

        //将链表转移到数组中
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }

        return arr;
    }

    /**
     * 创建链表
     * @param nums
     * @return
     */
    public static ListNode createListNode(int[] nums){
        //将第一个数作为头结点
        ListNode listNode = new ListNode(nums[0]);
        ListNode pointer = listNode;

        for (int i = 1; i < nums.length; i++) {
            //找尾结点
            while (pointer.next != null){
                //往后移动
                pointer = pointer.next;
            }

            //找到尾结点后添加数据
            pointer.next = new ListNode(nums[i]);
        }

        return listNode;
    }


    /**
     * 官方题解1
     */
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
